//
// Created by wdq on 2022/9/27.
//
#include <iostream>
#include <vector>
#include <random>

using namespace std;

#define LEVEL 10

struct SkipNode {
    int val;
    vector<SkipNode *> next;

    explicit SkipNode(int val = 0) : val(val), next(LEVEL, nullptr) {
    }

    friend ostream &operator<<(ostream &os, const SkipNode &node) {
        os << "val: " << node.val << " -> ";
        return os;
    }
};

struct SkipList {
    SkipNode *head;

    SkipList() {
        head = new SkipNode();
    }

    void find(int target, vector<SkipNode *> &prev) const {
        auto cur = head;
        for (int i = LEVEL - 1; i >= 0; i--) {
            while (cur->next[i] != nullptr && cur->next[i]->val < target) {
                cur = cur->next[i];
            }
            prev[i] = cur;
        }
    }

    bool search(int target) const {
        vector<SkipNode *> prev(LEVEL);
        this->find(target, prev);
        return prev[0]->next[0] != nullptr && prev[0]->next[0]->val == target;
    }


    void add(int target) const {
        vector<SkipNode *> prev(LEVEL);
        this->find(target, prev);
        auto temp = prev[0]->next[0];
        if (temp != nullptr && temp->val == target) {
            return;
        }
        auto node = new SkipNode(target);
        for (int i = 0; i < LEVEL; i++) {
            node->next[i] = prev[i]->next[i];
            prev[i]->next[i] = node;
            if (rand() % 2) break;

        }

    }

    bool erase(int target) const {
        vector<SkipNode *> prev(LEVEL);
        this->find(target, prev);
        auto node = prev[0]->next[0];
        if (node != nullptr && node->val == target) {
            for (int i = 0; i < LEVEL && prev[i]->next[i] == node; i++) {
                prev[i]->next[i] = node->next[i];
            }
            return true;
        }
        return false;

    }

    friend ostream &operator<<(ostream &os, const SkipList &list) {
        for (auto cur = list.head->next[0]; cur != nullptr; cur = cur->next[0]) {
            os << *cur;
        }
        os << endl;
        return os;
    }
};

int main() {
    SkipList skipList;
    for (int i = 0; i < 8; i++) {
        skipList.add(i);
    }
    cout << skipList;
    cout << skipList.search(1) << endl;
    cout << skipList.erase(1) << endl;
    cout << skipList;
    return 0;
}